//
// Created by liushuai on 2021/1/13.
//

#include "solve.h"
<<<<<<< HEAD:cxx/algorithm/src/solve.cc

std::string solve(int M, int N){
    std::string result = "";
    std::string final_result = "";
    std::vector<char> chars = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
    bool flag = true;
    if(M<0){
=======
#include <iostream>
#include <numeric>
std::string solve(int M, int N) {
    std::string result = "";
    std::string final_result = "";
    std::vector<char> chars = {'0', '1', '2', '3', '4', '5', '6', '7',
                               '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
    bool flag = true;
    if (M < 0) {
>>>>>>> dev:cxx/algorithm/common/src/solve.cc
        flag = false;
        M = -M;
    }

<<<<<<< HEAD:cxx/algorithm/src/solve.cc
    while (M){
        int res = M%N;
        result.push_back(chars[res]);
        M/=N;

    }
    if(!flag)
        final_result.push_back('-');
    for(auto iter = result.rbegin();iter!=result.rend();iter++){
=======
    while (M) {
        int res = M % N;
        result.push_back(chars[res]);
        M /= N;
    }
    if (!flag)
        final_result.push_back('-');
    for (auto iter = result.rbegin(); iter != result.rend(); iter++) {
>>>>>>> dev:cxx/algorithm/common/src/solve.cc
        final_result.push_back(*iter);
    }

    return final_result;
<<<<<<< HEAD:cxx/algorithm/src/solve.cc
}
=======
}
void solve(std::vector<std::vector<char>> &board) {
    if (board.size() == 0)
        return;

    int rows = board.size();
    int cols = board[0].size();

    // 用一个虚拟节点, 边界上的O 的父节点都是这个虚拟节点
    UnionFind *uf = new UnionFind(rows * cols + 1);
    int dummyNode = rows * cols;

    auto node = [&cols](int i, int j) { return i * cols + j; };
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (board[i][j] == 'O') {
                // 边界遇到O则合并连通区域
                if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
                    // 边界上的O,把它和dummyNode 合并成一个连通区域.
                    uf->Union(node(i, j), dummyNode);
                } else {
                    // 和上下左右合并成一个连通区域.
                    if (i > 0 && board[i - 1][j] == 'O')
                        uf->Union(node(i, j), node(i - 1, j));
                    if (i < rows - 1 && board[i + 1][j] == 'O')
                        uf->Union(node(i, j), node(i + 1, j));
                    if (j > 0 && board[i][j - 1] == 'O')
                        uf->Union(node(i, j), node(i, j - 1));
                    if (j < cols - 1 && board[i][j + 1] == 'O')
                        uf->Union(node(i, j), node(i, j + 1));
                }
            }
        }
    }

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (uf->isConnected(node(i, j), dummyNode)) {
                // 和dummyNode 在一个连通区域的,那么就是O；
                board[i][j] = 'O';
            } else {
                board[i][j] = 'X';
            }
        }
    }
    delete uf;
}
>>>>>>> dev:cxx/algorithm/common/src/solve.cc
